package leetcode.list;

/**
 * Created by zxc on 2018/9/27.
 * 反转一个单链表。LeetCode206  92
 * 输入: 1->2->3->4->5->NULL   输出: 5->4->3->2->1->NULL 简单的链表逆序
 */
public class ReverseList {
     // Definition for singly-linked list.
     static class ListNode {
         int val;
         ListNode next;
         ListNode(int x) {
             val = x;
         }
     }

     /*简单的链表逆序*/
    private static ListNode reverseListA(ListNode head) {
        ListNode tmpNode = null;
        ListNode newNode = null;
        while (head != null){
            tmpNode = head.next;
            head.next = newNode;
            newNode = head;
            // 遍历链表
            head = tmpNode;
        }
        return newNode;
    }

    /*将链表从位置m到n逆序*/
    private static ListNode reverseListB(ListNode head, int m, int n) {
        int changeLength = n-m+1;
        ListNode preHead = null;
        ListNode result = head;
        while(head !=null && (--m) !=0){
            preHead = head;
            head = head.next;
        }
        // 子链表逆序后的链表尾节点
        ListNode modifyTail = head;
        ListNode newHead = null;
        while(head != null && changeLength != 0){
            ListNode tmpNext = head.next;
            head.next = newHead;
            newHead = head;
            head = tmpNext;
            changeLength--;
        }
        // 逆序子链表后的第一个节点
        modifyTail.next = head;
        if(preHead != null){
            // m > 1,不是从第一个节点开始逆序的
            preHead.next = newHead;
        }else{
            result = newHead;
        }
        return result;
    }

    /*将链表从位置m到n逆序  自己编写的*/
    private static ListNode reverseListC(ListNode head, int m, int n) {
        //链表m位置前的首尾存储位置
        ListNode preHeadNode = head;
        ListNode preTailNode = null;
        //链表n+1位置的首存储位置
        ListNode behHeadNode = null;
        //未交换前链表m-n位置的首尾存储位置
        ListNode midHeadNode = null;
        ListNode midTailNode = null;
        //交换后链表m-n位置的首尾存储位置
        ListNode midHeadNodeN = null;
        ListNode midTailNodeN = null;
        //中间临时变量初始化
        ListNode tmpNode = null;
        int tmp = 1;

        //截取出m-n的子链表，最后一个节点next置为null
        while (head != null && (tmp != m)){
            if(tmp == (m-1)){
                preTailNode = head;
            }
            head = head.next;
            ++tmp;
        }

        midHeadNode = head;
        while (head != null && (tmp != n)){
            head = head.next;
            ++tmp;
        }
        // 此时head处于未交换子链的最后一个节点
        midTailNode = head;
        behHeadNode = midTailNode.next;
        midTailNode.next =null;

        //子链的首节点反转后将为尾节点
        midTailNodeN = midHeadNode;
        while (midHeadNode != null){
            tmpNode = midHeadNode.next;
            midHeadNode.next = midHeadNodeN;
            midHeadNodeN = midHeadNode;
            // 遍历链表
            midHeadNode = tmpNode;
        }

        if(preTailNode != null){
            preTailNode.next = midHeadNodeN;
        }
        midTailNodeN.next = behHeadNode;

        if(m == 1){
            preHeadNode = midHeadNodeN;
        }
        return preHeadNode;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;
        node7.next=null;
        ListNode head = node1;

        /*ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=null;
        ListNode head = node1;*/

        System.out.println("Before reverse：");
        while (head!=null){
            System.out.print(head.val+">");
            head = head.next;
        }
        System.out.println("end");

        /*简单的链表逆序*/
        //ListNode newHead = reverseListA(node1);

        /*将链表从位置m到n逆序*/
        ListNode newHead = reverseListB(node1, 1, 7);

        head = newHead;
        System.out.println("After reverse：");
        while (head!=null){
            System.out.print(head.val+">");
            head = head.next;
        }
        System.out.println("end");
    }




}
